/*
 * COMP6471 Project
 *  
 * This file is created by Yuan Tao (ewan.msn@gmail.com)
 * Licensed under GNU GPL v3
 * 
 * $Author: ewan.msn@gmail.com $
 * $Date: 2011-12-03 21:16:31 +0000 (Sat, 03 Dec 2011) $
 * $Rev: 68 $
 * $HeadURL: http://comp6471.googlecode.com/svn/Project6/src/kklib/Layout.java $
 * 
 */

package kklib;

import java.util.ArrayList;

import utils.SysLogger;

public class Layout {
	// attributes of the txt file.
	public String fileFullname;
	public ArrayList<String> txtFileData = new ArrayList<String>();
	public ArrayList<String> txtFileFormulas = new ArrayList<String>();	// all the cages formulas in string
	
	// attributes of the layout
	public static final int MAX_GAME_SIZE = 6;
	public String gameName;
	public int gameSize = 4;
	public ArrayList<Cage> cages = new ArrayList<Cage>();
	private int numOfSolutions;			// number of possible solutions
	public static final int MAX_SOLUTIONS = 64;
	
	// to store the cells by connecting them in rows or columns
	public ArrayList<Cell> rows = new ArrayList<Cell>();
	public ArrayList<Cell> columns = new ArrayList<Cell>();
	
	
	// get property
	public int getNumOfSolutions() {
		return numOfSolutions;
	}
	
	// find the cell by its coordinate
	public Cell findCellByXY(int x, int y) {
		for (int i = 0; i < cages.size(); i++) {
			ArrayList<Cell> cells = cages.get(i).cells;
			
			for (int j = 0; j < cells.size(); j++) {
				if (cells.get(j).x == x && cells.get(j).y == y) {
					return cells.get(j);
				}
			}
		}
		
		return null;
	}
	
	// store the cells by rows and columns
	private String getCellTxtCoordinate(int x, int y) {
		return Character.toString((char) ('A' - 1 + y)) + (char) ('0' + x);
	}
	public int sortCells() {
		for (int i = 1; i <= gameSize; i++) {
			for (int j = 1; j <= gameSize; j++) {
				Cell c = findCellByXY(i, j);
				if (c == null) {
					SysLogger.parserErr(fileFullname, "The cell(" + getCellTxtCoordinate(i, j) + ") is missing.");
					return -1;
				}
				columns.add(c);
				
				if (i == j) {
					rows.add(c);
				} else {
					c = findCellByXY(j, i);
					if (c == null) {
						SysLogger.parserErr(fileFullname, "The cell(" + getCellTxtCoordinate(j, i) + ") is missing.");
						return -1;
					}
					rows.add(c);
				}
			}
		}
		return 0;
	}
	
	/*
	 *  check if the layout is validity
	 *  case1: cells number should be equal to the number of the grids of layout
	 *  case2: no same cells
	 *  case3: the cage should be validity. all the cells of the cage are connected.
	 */
	public int syntaxChecker() {
		int cellNum = 0;
		
		// case1
		for (int i = 0; i < cages.size(); i++) {
			cellNum += cages.get(i).cageSize;
		}
		if (cellNum != (gameSize * gameSize)) {
			SysLogger.parserErr(fileFullname, "Too less or too many cells. Cells in total: "
					+ cellNum + " but GameSize is: " + gameSize);
			return -1;
		}
		
		// case2
		if (sortCells() != 0) {
			return -1;
		}
		
		// case3
		for (int i = 0; i < cages.size(); i++) {
			if (cages.get(i).cageSize < 2) {
				continue;
			}

			ArrayList<Cell> cells = cages.get(i).cells;
			
			for (int j = 0; j < cells.size(); j++) {
				// TODO: skip the one that already compared.
				
				Cell c = cells.get(j);
				boolean ifConnected = false;
				StringBuffer cellMsg = new StringBuffer();
				
				cellMsg.append("(" + getCellTxtCoordinate(c.x, c.y) + ") ");
				for (int k = 0; k < cells.size(); k++) {
					if (k == j) {
						continue;						
					}
					if (c.x == cells.get(k).x || c.y == cells.get(k).y) {
						ifConnected = true;
						break;
					}
					cellMsg.append("(" + getCellTxtCoordinate(cells.get(k).x, cells.get(k).y) + ") ");
				}
				if (!ifConnected) {
					SysLogger.parserErr(fileFullname, "Cells " + cellMsg.toString() 
							+ "cannot make up a cage.");
					return -1;
				}
			}
		}
		return 0;
	}
	
	// add data to cells for printing
	public int addDataToCells() {
		int pad = 1;
		
		for (int i = 0; i < cages.size(); i++) {
			ArrayList<Cell> c = cages.get(i).cells;
			for (int j = 0; j < c.size(); j++) {
				c.get(j).data = pad;
			}
			pad++;
		}
		return 0;
	}
	
	// check if there is a right solution
	public int checkSolution() {
		// if all the cells have value
		for (int i = 0; i < rows.size(); i++) {
			if (rows.get(i).value == 0) {
				return 1;
			}
		}
		
		// if each number is used only once by row and column
		// TODO: the following algorithm needs to be approved
		int numSum = 0, rowSum = 0, colSum = 0, numMulSum = 1, rowMulSum = 1, colMulSum = 1;
		
		for (int i = 0; i < gameSize; i++) {
			numSum += i + 1;
			numMulSum *= i + 1;
		}
		for (int i = 0; i < gameSize; i++) {
			rowSum = 0;
			colSum = 0;
			rowMulSum = 1; 
			colMulSum = 1;
			for (int j = 0; j < gameSize; j++) {
				rowSum += rows.get(i * gameSize + j).value;
				rowMulSum *= rows.get(i * gameSize + j).value;
				colSum += rows.get(j * gameSize + i).value;
				colMulSum *= rows.get(j * gameSize + i).value;
			}
			if (numSum != rowSum || numSum != colSum 
					|| numMulSum != rowMulSum || numMulSum != colMulSum) {
				return -1;
			}
		}
		
		// if the cells values satisfy the cage formula.
		for (int i = 0; i < cages.size(); i++) {
			Cage c = cages.get(i);
			int ret = 0;
			
			switch (c.operator) {
			case Cage.OP_EQU:
				if (c.cells.get(0).value != c.targetNumber) {
					return -1;
				}
				break;
			case Cage.OP_ADD:
			case Cage.OP_MUL:
				for (int j = 0; j < c.cells.size(); j++) {
					if (c.operator == Cage.OP_ADD) {
						ret += c.cells.get(j).value;
					} else {
						if (ret == 0) {
							ret = 1;
						}
						ret *= c.cells.get(j).value;
					}
				}
				if (ret != c.targetNumber) {
					return -1;
				}
				break;
			case Cage.OP_SUB:				
			case Cage.OP_DIV:
				int indexOfMaxOne = 0;
				
				ret = c.targetNumber;
				for (int j = 0; j < c.cells.size() - 1; j++) {
					if (c.cells.get(j).value > c.cells.get(j + 1).value) {
						indexOfMaxOne = j;
					} else {
						indexOfMaxOne = j + 1;
					}
				}
				for (int j = 0; j < c.cells.size(); j++) {
					if (j == indexOfMaxOne) {
						continue;
					}
					if (c.operator == Cage.OP_SUB) {
						ret += c.cells.get(j).value;
					} else {
						ret *= c.cells.get(j).value;
					}
				}
				if (ret != c.cells.get(indexOfMaxOne).value) {
					return -1;
				}
				break;
			}		
		}
		return 0;
	}
	
	// set a cell value
	public int setCellValue(String cellName, int val, int type) {
		char ch = cellName.charAt(0);
		int index = 0;
		
		// get the index
		SysLogger.info("setCellVal: " + cellName + ":" + val);
		if (ch < 'A' || ch > 'A' + gameSize - 1) {
			return -1;
		}
		index = (ch - 'A') * gameSize;
		
		ch = cellName.charAt(1);
		if (ch < '1' || ch > '1' + gameSize - 1) {
			return -1;
		}
		index += ch - '1';
		
		if (index >= rows.size()) {
			return -2;
		}
		
		// set value to the cell
		if (type == 1) {
			rows.get(index).value = val;
		} else {
			// TODO: if there is no value, set the value instead of possible value
			if (val == 0) {
				rows.get(index).possibleValues.clear();
			} else {
				if (rows.get(index).possibleValues.size() > 5) {
					rows.get(index).possibleValues.remove(0);   // remove the first one
				}
				rows.get(index).possibleValues.add(val);
			}
		}
		
		// refresh the data which will be used by UI
		rows.get(index).possValues = "";
		for (int i = 0; i < rows.get(index).possibleValues.size(); i++) {
			rows.get(index).possValues += rows.get(index).possibleValues.get(i);
		}
		
		return 0;
	}
	
	
	// The following code is copied from project 4, in order to get a solution.
	
	private void deleteValsByRowsAndColumns(Cell c) {		
		Cell tmpCell = null;
		
		// search the cells in the same column.
		for (int i = 1; i <= gameSize; i++) {
			tmpCell = rows.get(gameSize * (i - 1) + c.x - 1);
			// delete the values exist in the above cells within the same column.
			if (i < c.y) {
				Integer val = tmpCell.value;
				c.possibleValues.remove(val);
				
			// remove the values in the cage whose size is 1
			} else if (i > c.y) {
				if (tmpCell.cage.cageSize == 1) {
					Integer val = tmpCell.cage.targetNumber;
					c.possibleValues.remove(val);
				}
			}
		}		
		
		// search the cells in the same row
		for (int i = 1; i <= gameSize; i++) {
			tmpCell = rows.get(gameSize * (c.y - 1) + i - 1);
			// delete the values exist in the left cells within the same row
			if (i < c.x) {
				Integer val = tmpCell.value;
				c.possibleValues.remove(val);
			
			// 
			} else if (i > c.x) {
				if (tmpCell.cage.cageSize == 1) {
					Integer val = tmpCell.cage.targetNumber;
					c.possibleValues.remove(val);
				}
			}
		}
	}
	
	// set possible values for the last cell of the cage which has SUB or DIV operator
	private int setLastCellofSUBDIVCage(Cage pCage, Cell c) {
		ArrayList<Cell> arrCells = pCage.cells;
		int maxVal = pCage.targetNumber;
		int bigResult = pCage.targetNumber;		
		int smlResult = (pCage.operator == Cage.OP_SUB ? 0 : 1);
		boolean ifTgtSmaller = false;	// if targetnumber is smaller than one of the values of cells

		for (int i = 0; i < arrCells.size(); i++) {
			int cellVal = arrCells.get(i).value;

			if (cellVal == 0) {
				continue;
			}
			// get the bigger possible value of the cell
			if (pCage.operator == Cage.OP_SUB) {
				bigResult += cellVal;
			} else {
				bigResult *= cellVal;
			}

			// get the smaller one
			if (maxVal > cellVal) {
				if (pCage.operator == Cage.OP_SUB) {
					smlResult += cellVal;
				} else {
					smlResult *= cellVal;
				}
			} else {
				if (pCage.operator == Cage.OP_SUB) {
					smlResult += maxVal;
				} else {
					smlResult *= maxVal;
				}
				maxVal = cellVal;
				ifTgtSmaller = true;
			}
		}

		if (bigResult > 0 && bigResult <= gameSize) {
			c.possibleValues.add(bigResult);
		}

		if (ifTgtSmaller) {
			if (pCage.operator == Cage.OP_SUB) {
				smlResult = maxVal - smlResult;
			} else {
				int tmp = smlResult;
				
				tmp = maxVal / smlResult;		// should not be a float
				if (maxVal != tmp * smlResult) {
					smlResult = 0;
				} else {
					smlResult = tmp;
				}
			}
			if (smlResult > 0 && smlResult <= gameSize) {
				c.possibleValues.add(smlResult);
			}
		}
		
		return c.possibleValues.size();
	}

	/*
	 * return value: positive integer means the number of the possible values,
	 * negative integer means the reason why there is no possible value
	 */
	private int getPossibleValues(Cell c) {
		int numOfValues = c.possibleValues.size();
		
		if (numOfValues > 0) {
			return numOfValues;
		}
		
		// if the cell has been set a value
		if (c.value != 0) {
			return -1;		// go back to the left cell
		}
		
		// obviously no solutions
		Cage pCage = c.cage;
		if ((pCage.operator == Cage.OP_SUB && pCage.targetNumber >= gameSize)
			|| (pCage.operator == Cage.OP_DIV && pCage.targetNumber > gameSize)) {
			return -4;
		}
		
		// a cage with only one cell
		if (pCage.operator == Cage.OP_EQU) {
			c.possibleValues.add(c.cage.targetNumber);
			return 1;
		}
		
		// add all the possible values by the rule of the cage
		// NOTE: Each cell MUST have one possible value.
		// first, get the first possible value for cage with ADD & MUL operator
		ArrayList<Cell> arrCells = pCage.cells;
		int resultVal = pCage.targetNumber;
		int numOfCellsWithVal = 0;
		
		for (int i = 0; i < arrCells.size(); i++) {
			// just compared the cells of the cage prior to current one
			if (!(arrCells.get(i).x <= c.x && arrCells.get(i).y <= c.y)) {
				continue;
			}
			int cellVal = arrCells.get(i).value;
			
			if (cellVal == 0) {
				continue;
			}
			numOfCellsWithVal++;
			switch (pCage.operator) {
			case Cage.OP_ADD:
				resultVal -= cellVal;
				break;
			case Cage.OP_MUL:
				int tmp = resultVal;
				
				tmp /= cellVal;
				if (resultVal != tmp * cellVal) {		// should not be a float
					// go back to the last cell of the cage.
					return -3;
				}
				resultVal = tmp;
				break;
			}
		}
		
		// If it is the last one of the cage
		if (pCage.cageSize - 1 == numOfCellsWithVal) {
			if ((resultVal < 1 && pCage.operator == Cage.OP_ADD) || resultVal > gameSize) {
				// go back to the last cell of the cage.
				return -3;		
			}
			if (pCage.operator == Cage.OP_SUB || pCage.operator == Cage.OP_DIV) {
				// set possible values for the last cell 
				if (setLastCellofSUBDIVCage(pCage, c) == 0) {
					return -3;
				}
			} else {
				c.possibleValues.add(resultVal);
			}
			deleteValsByRowsAndColumns(c);
			return c.possibleValues.size();
		}
		
		// else, add all the other possible values
		switch (pCage.operator) {
		case Cage.OP_ADD:
			if (pCage.cageSize - numOfCellsWithVal > 1) {
				resultVal--;	// the smallest value of the last cell should be 1.
			}
			if (resultVal > gameSize) {
				resultVal = gameSize;
			}
			while (resultVal > 0 && resultVal <= gameSize) {
				c.possibleValues.add(resultVal--);
			}
			break;
		case Cage.OP_MUL:
			if (resultVal > gameSize) {
				resultVal = gameSize;
			}
			while (resultVal > 0 && resultVal <= gameSize) {
				int tmp = pCage.targetNumber / resultVal;
				
				if (pCage.targetNumber == tmp * resultVal) {
					// the targetNumber can be divided by the possible value in integer. 
					c.possibleValues.add(resultVal);
				}
				resultVal--;
			}
			break;
		case Cage.OP_SUB:
		case Cage.OP_DIV:
			resultVal = 1;
			while (resultVal <= gameSize) {
				c.possibleValues.add(resultVal++);
			}
			break;
		}
		deleteValsByRowsAndColumns(c);
		
		return c.possibleValues.size();
	}

	private Cell getLeftCell(Cell c) {
		if (c.x == 1 && c.y == 1) {
			return null;
		}
		return rows.get(gameSize * (c.y - 1) + c.x - 2);
	}
	
	private Cell getRightCell(Cell c) {
		if (c.x == gameSize && c.y == gameSize) {
			return null;
		}
		return rows.get(gameSize * (c.y - 1) + c.x);
	}
	
	private Cell getCellofLastRow(Cell c) {
		if (c.y == 1) {
			return null;
		}
		return rows.get(gameSize * (c.y - 2) + c.x - 1);
	}
	
	// search the cage from right to left, down to up
	private Cell getLastCellofCage(Cell c) {
		if (c.x == 1 && c.y == 1) {
			return null;
		}

		int i = gameSize * (c.y - 1) + c.x - 2;
		Cell leftCell = null;
		
		while (i >= 0) {
			leftCell = rows.get(i);
			if (c.cage == leftCell.cage) {
				return leftCell;
			}
			i--;
		}
		return null;	// do not find the cell.
	}
	
	/*
	 * Recursively set the cell value with all the possible values 
	 * from left to right, up to down.
	 */
	private int try2SetCellValue(Cell c) {
		if (c == null) {
			return -1;
		}
		
		int ret = getPossibleValues(c); 
		
		if (ret > 0) {
			// set a possible value to the cell
			c.value = c.possibleValues.get(0);
			c.possibleValues.remove(0);

			// if it is the last cell
			if (c.x == gameSize && c.y == gameSize) {
				// Succeed finding one solution
				numOfSolutions++;
				
				if (numOfSolutions > 0) {
					return numOfSolutions;
				}
				
				// try to test the next possible value of the same cell
				return try2SetCellValue(c);
			}
			
			// clear the possibleValues of the next cell in order to get the new possibleValues
			Cell nextCell = getRightCell(c);
			nextCell.possibleValues.clear();
			nextCell.value = 0;
			//logger.printSolution(this, c);
			return try2SetCellValue(nextCell);
		}
		
		// find no possible value
		if (ret == -4) {
			return -4;
		} else if (ret == -3) {
			return try2SetCellValue(getLastCellofCage(c));
		} else if (ret == -2) {
			return try2SetCellValue(getCellofLastRow(c));
		} else {
			if (c.x == 1 && c.y == 1) {
				return 0;		// Over. All the possible values have been tried.
			}
			return try2SetCellValue(getLeftCell(c));
		}		
	}
	
	public int setRightValues() {
		try {
			if (gameSize == 6) {
				rows.get(0).possibleValues.add(1);
			}
			try2SetCellValue(rows.get(0));
		} catch (StackOverflowError e) {
			SysLogger.err("getNumOfPossibleSolutions: StackOverflowError");
			return -1;
		}
		
		if (numOfSolutions < 1) {
			return -1;
		}

		// store and clear the data
		for (int i = 0; i < cages.size(); i++) {
			for (int j = 0; j < cages.get(i).cells.size(); j++) {
				cages.get(i).cells.get(j).possibleValues.clear();
				cages.get(i).cells.get(j).rightVal = cages.get(i).cells.get(j).value;
				cages.get(i).cells.get(j).value = 0;
			}
		}

		return 0;
	}
	
}
